Технология ATM

3.3. RED в сетях ATM
   Управление трафиком является ключевым компонентом стабильной работы ATM-сетей. В общем случае существуют два типа управления – превентивный и адаптивный.
   Превентивный контроль базируется на соблюдении трафик-контракта. Источник трафика должен "вписаться" в заранее оговоренные рамки качества обслуживания с помощью, например, широко известных механизмов контроля Leaky Bucket и Virtual Scheduling. Превентивный контроль применяется в основном для CBR и VBR, в которых характеристики трафика известны или поддаются прогнозированию.
   Адаптивный контроль основан на использовании свободной полосы пропускания. Обычно он реализуется для ABR и UBR, которые не имеют жестких требований к качеству обслуживания. Адаптивный контроль осуществляется с помощью обратной связи между источником и коммутатором ATM, которая может быть явной (для передачи информации о перегрузках применяются специальные ячейки, как в ABR) или скрытой (поведение источника трафика меняется в соответствии с изменением поведения сети).
    Алгоритм RED в сетях ATM использует скрытую обратную связь для уведомления о перегрузках путем выборочного уничтожения ячеек пользователя. Вместо того чтобы дожидаться перегрузки и переполнения буферов, следствием чего станет уничтожение всех поступающих данных, RED уничтожает часть поступающих ячеек. Их число и частота уничтожения определяются параметром, называемым вероятностью уничтожения (Pa). Этот параметр рассчитывается каждый раз в соответствии с текущим состоянием ресурсов ATM-коммутатора, т.е. фактически определяется длиной очереди на обслуживание трафика в ATM-коммутаторе.

Средняя длина очереди (QueueLength) рассчитывается так:

QueueLength=(1-1/2n)• PreviousQueueLength+CurrentQueueLength•1/2n.

Здесь PreviousQueueLength – длина очереди при предыдущем подсчете; CurrentQueueLength – текущая длина очереди; n – весовой коэффициент (n>1), который определяет администратор сети, исходя из следующих соображений.
Если n имеет малое значение, средняя длина очереди QueueLength фактически определяется текущей длиной очереди CurrentQueueLength. Тогда алгоритм RED четко и быстро реагирует на любые изменения текущей длины очереди, что позволяет ATM-коммутатору практически мгновенно избавляться от лишних ячеек при малейшей опасности перегрузки. Однако при очень малых значениях n RED станет необоснованно сбрасывать ячейки даже при небольших временных увеличениях очередей, которые не представляют опасности и могут быть обработаны без потерь.
Если коэффициент n имеет большое значение, средняя длина очереди QueueLength становится функцией от предыдущей длины очереди PreviousQueueLength. Алгоритм RED достаточно медленно реагирует на изменения длины очереди, что позволяет ATM-коммутатору как бы сглаживать "пики" и "провалы" трафика без удаления ячеек. Но при очень больших значениях n RED может оказаться настолько медлительным, что будет продолжать уничтожение ячеек, даже когда длина очереди станет меньше минимального порога срабатывания этого алгоритма.

Работу алгоритма RED можно описать следующим образом:

Если средняя длина очереди QueueLength меньше либо равна минимально допустимому значению порога срабатывания MinThreshold алгоритма RED (QueueLength<MinThreshold), то поступающая ячейка будет обслужена ATM-коммутатором.
Если средняя длина очереди QueueLength находится внутри некоторого предопределенного диапазона (MinThreshold < QueueLength < MaxThreshold), то RED начнет уничтожать некоторую часть ячеек. Доля уничтожаемых ячеек определяется значением Pa, рассчитываемым в соответствии с состоянием ресурсов коммутатора. Пересчет вероятности Pa и сам процесс отбрасывания ячеек будут продолжаться до тех пор, пока значение средней длины очереди QueueLength не опустится ниже минимального порога MinThreshold.

Вероятность уничтожения пакетов Pa подсчитывается следующим образом:

Pa=Pb/(1-Count • Pb). (1)

Здесь

Pb=Pmax•(QueueLength-MinThreshold)/(MaxThreshold-MinThreshold)•PacketSize/MaxPacketSize, (2)

где Pmax – максимальная вероятность уничтожения ячеек; Count – количество ячеек, помещенных в очередь с момента последнего сброса; PacketSize – длина пакета протокола, инкапсулированного в ATM; MaxPacketSize – максимальная длина пакета, инкапсулированного в ATM.
   Если средняя длина очереди QueueLength больше или равна максимально допустимому значению MaxThreshold (QueueLength > MaxThreshold), то поступившая на вход коммутатора ячейка обязательно будет уничтожена.
   Как видно из формул (1) и (2), вероятность уничтожения ячеек Pa зависит от размеров инкапсулированных пакетов. Следовательно, большие пакеты (например, при перекачке файлов по протоколу FTP) будут уничтожатся чаще, чем маленькие (например, передаваемые по telnet).
   В сетях ATM используются две модификации алгоритма RED: C-RED (Cell-RED) работает с каждой ячейкой, P-RED (Packet-RED) – с группой ячеек, образующих AAL5 PDU.
   Алгоритм C-RED учитывает каждую отдельную ячейку и, таким образом, имеет полную картину состояния сети в каждый момент. Недостаток данного алгоритма – сложность его реализации при работе на больших скоростях. В высокоскоростных сетях ATM процедура пересчета средней длины очереди QueueLength при появлении каждой новой ячейки может оказаться достаточно сложной и дорогостоящей, поэтому в них обычно используется P-RED.
    Алгоритм P-RED работает с группой ячеек, которые образуют один пакет, инкапсулированный в ATM (например, IP-пакет). Пересчет средней длины очереди осуществляется для всех ячеек пакета только один раз – в момент поступления первой ячейки. P-RED не является таким гибким, как C-RED, но зато вполне может быть реализован на самых высокоскоростных каналах.
    Среди недостатков алгоритма RED при работе в сети ATM нужно отметить следующий. RED сбрасывает только одну или несколько ячеек из тех, которые образуют исходный пакет. Передача по сети остальных ячеек (неполного пакета) продолжается, они будут уничтожены только в приемнике на уровне адаптации AAL5. Эту проблему позволяет решить алгоритм Partial Packet Discard PPD, который обеспечивает удаление неполных пакетов.
     В алгоритме RED вероятность уничтожения пакета является функцией от его размера – см. формулы (1) и (2). Размеры передаваемых пакетов определяются динамически в процессе передачи через ATM-коммутатор. В AAL5 границы пакета определяются значением поля PTI в заголовке ячейки, помечающего последнюю ячейку пакета. Поскольку определить размер еще не принятого пакета нельзя, его считают равным размеру последнего пакета, принятого по данному виртуальному каналу. Таким образом, удается использовать зависимость вероятности уничтожения ячейки от количества ячеек, образующих исходный пакет AAL5 PDU, т. е. от размера пакета (что не имеет места в алгоритме EPD).
    В случае широкого диапазона колебаний нагрузки алгоритм RED может не отреагировать на переполнение буферов, поэтому он обычно применяется совместно с алгоритмом EPD. Последний осуществляет не выборочное уничтожение одной ячейки, а сброс целого пакета, что позволяет резко снизить нагрузку на ATM-коммутатор.

Рис.5 Структурная схема работы совместно реализованных алгоритмов P-RED и EPD.

    При появлении ячейки ATM-коммутатор анализирует (используя поле PTI заголовка), является ли она первой ячейкой пакета AAL5 PDU. Если ячейка является началом пакета, ATM-коммутатор пересчитывает среднюю длину очереди QueueLength (как уже было отмечено, в алгоритме P-RED пересчет длины очереди осуществляется только для первой ячейки пакета).
    Если длина очереди меньше либо равна минимальному порогу срабатывания алгоритма RED (QueueLength<MinThreshold), то данная и все последующие ячейки, принадлежащие данному пакету, будут по мере поступления обслужены ATM-коммутатором. Если средняя длина очереди QueueLength находится в пределах MinThreshold<QueueLength<MaxThreshold, то подсчитывается вероятность уничтожения ячеек Pa, система переходит в состояние уничтожения ячеек и осуществляет сброс поступающих ячеек с частотой, определяемой вероятностью Pa.
     У читателя может возникнуть законный вопрос: зачем нужно использовать алгоритм RED, подсчитывающий вероятность уничтожения ячеек внутри пакета, если алгоритм PPD, вступающий в работу следом, уничтожает остатки пакета невзирая на любые значения вероятности Pa. Основным достоинством алгоритма RED является возможность подсчета для каждого виртуального соединения вероятности уничтожения ячеек в зависимости от размера пакетов (AAL5 PDU), передаваемых по данному виртуальному соединению. Чем больше пакеты, тем выше вероятность их уничтожения. Это позволяет справедливо распределять полосу пропускания между потоками данных различных пользователей, чего нельзя достичь, используя алгоритмы EPD/PPD самостоятельно, а не совместно с RED.
     Наконец, если длина очереди превосходит предельно допустимое значение MaxThreshold (QueueLength>MaxThreshold), то сразу же включается алгоритм EPD, способный достаточно быстро и эффективно снять перегрузку путем одновременного удаления большого числа ячеек.

{назад [на главную] вперёд}